#include <iostream>
#include <vector>
#include <memory>
#include <queue>
using namespace std;


class Solution {
public:
	struct TreeNode
	{
		TreeNode* left = nullptr;
		TreeNode* right = nullptr;
		int val;
		TreeNode(int v) : val(v){}
	};

	TreeNode* dfs(vector<int>& arr, int start, int end)
	{
		if (start > end) return nullptr;
		int mid = (start + end) >> 1;
		TreeNode* root = new TreeNode(arr[mid]);

		root->left = dfs(arr, start, mid - 1);
		root->right = dfs(arr, mid + 1, end);

		return root;
	}

	vector<int> LevelOrder(vector<int>& arr)
	{
		int n = arr.size();
		if (n <= 1) return arr;
		TreeNode* root = dfs(arr, 0, n - 1);

		vector<int> ans;
		queue<TreeNode*> qu;
		qu.push(root);

		while (!qu.empty())
		{
			int levelsz = qu.size();
			for(int i = 0; i < levelsz; ++i)
			{
				TreeNode* head = qu.front();
				qu.pop();
				ans.emplace_back(head->val);

				if (head->left) qu.push(head->left);
				if (head->right) qu.push(head->right);
			}
		}
		deleteTree(root);

		for (auto& e : ans)
		{
			cout << e << " ";
		}
		return ans;
	}
	void deleteTree(TreeNode* root) {
		if (!root) {
			return;
		}
		deleteTree(root->left);
		deleteTree(root->right);
		delete root;
	}
};





int main()
{
    Solution sol;
	vector<int> inorder_sequence = { 1, 2, 3, 4, 5, 6, 7 };

	vector<int> ret = sol.LevelOrder(inorder_sequence);

	return 0;
}


